package com.ssh;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;

public class NumSquares_279 {
	
 	public int numSquares1(int n) {
        int dp[] = new int[n+1];
        for(int i = 1; i<=n; i++) 
            dp[i] = min(dp, i);
        
        return dp[n];
    }
    
    public int min(int dp[], int i) {
        int min = Integer.MAX_VALUE;
        int closest = (int)Math.sqrt(i); //starting with the biggest square root for i
        while(closest>=1) {
        	System.out.println("min="+min);
        	System.out.println("i="+i);
        	System.out.println("closest="+closest);
        	System.out.println("dp["+(i - closest*closest)+"]1="+dp[i - closest*closest]);
            min = Math.min(min, 1 + dp[i - closest*closest]); //adding 1 for perfect square
            System.out.println("min2="+min);
            closest--; //reducing closest for e.g. 12 => 9 + 1 + 1 + 1 here closest = 3 OR 12 => 4 + 4 + 4 here closest = 2
        }
        return min;
    }
    
    public int numSquares2(int n) {
    	List<Integer> list = generateSquares2(n);
    	Queue<Integer> queue = new LinkedList<>();
    	boolean[] marked = new boolean[n + 1];
    	queue.add(n);
    	int len = 0;
    	while (!queue.isEmpty()) {
    		len++;
    		int size = queue.size();
    		while (size-- > 0) {
    			int cur = queue.poll();
    			for (int x : list) {
    				int next = cur - x;
    				if (next < 0) {
    					continue;
    				}
    				if (next == 0) {
    					return len;
    				}
    				if (marked[next] == true) {
    					continue;
    				}
    				marked[next] = true;
    				queue.add(next);
    			}
    		}
    	}
		return n;
    }
    
    private List<Integer> generateSquares2(int n){
    	List<Integer> list = new ArrayList<>();
    	for (int i = 1; i*i <= n; i++) {
    		list.add(i*i);
    	}
    	return list;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
	
    public int numSquares(int n) {
        List<Integer> squares = generateSquares(n);
        Queue<Integer> queue = new LinkedList<>();
        boolean[] marked = new boolean[n + 1]; 
        queue.add(n);
        marked[n] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++; 
            while (size-- > 0) { 
                int cur = queue.poll(); 
                System.out.println("cur="+cur);
                for (int s : squares) {
                	System.out.println("s="+s);
                    int next = cur - s; 
                    System.out.println("next="+next);
                    if (next < 0) { 
                        break; 
                    } 
                    if (next == 0) { 
                        return level; 
                    } 
                    if (marked[next]) { 
                        continue;
                    }
                    marked[next] = true; 
                    queue.add(cur - s);
                }
            }
        }
        return n;
    }
 /** * 生成小于 n 的平方数序列 * @return 1,4,9,... */
 private List<Integer> generateSquares(int n) {
     List<Integer> squares = new ArrayList<>();
     int square = 1; 
     int diff = 3;
     while (square <= n) { 
         squares.add(square);
         square += diff;
         diff += 2; 
     } 
     return squares;
 }
    
	@Test
	public void test() {
		System.out.println(numSquares(12));
	}
	
}
